/*
 * tree_as_list.c
 *
 *  Created on: May 21, 2013
 *      Author: ILYA
 */

#include "tree_as_list.h"
#include "CRTP_ARP_table.h"

int flash_address = 0;
unsigned char arp_current_time;
unsigned char last_added_TreeNode;
/*current time*/
Timer_Tik t_current;
/*the time on preview of current time (last time)*/
Timer_Tik t_last;
/*the time on preview 255*unique time of current time (last time)*/
Timer_Tik t_last_last;
/*the nodes, which added, the last time (t_last_last ... t_current)*/
char last_added_nodes_count;
/*the nodes, which added, the last time at last time (t_last_last_last ... t_last_last)*/
char last_last_added_nodes_count;

TreeNode *rootInTree;

/*before using anything from this module you must call this function*/
void init_treeNode(int address, TreeNode **return_x)
{
	last_added_nodes_count = 0;
	last_last_added_nodes_count = 0;
	t_current = t_last = t_last_last = 0;
	flash_address = address;
	arp_current_time = 0;
	static TreeNode *treeNode;
	treeNode = (TreeNode *)malloc(sizeof(TreeNode));
	/*the root treeNode has an unique "TSN_7_12" serial number,
	 * which must be an average serial number, for decreasing searching time,
	 * this one field (first row) is not usable for saving any other treeNode*/
	memset(&treeNode->serialNumber, '\0', sizeof(struct UniqueSerialNumber));
	treeNode->Link_ID = ROOT_LINK_ID;
	treeNode->left = POINTER_ON_NULL;
	treeNode->right = POINTER_ON_NULL;
	treeNode->top = POINTER_ON_NULL;
	last_added_TreeNode = ROOT_LINK_ID;
	treeNode->next = POINTER_ON_NULL;
	treeNode->prev = POINTER_ON_NULL;
	treeNode->timer = 0;
	write_intoFlash(treeNode);
	*return_x = rootInTree = treeNode;
}

char treeNode_memcmp(struct UniqueSerialNumber value_sn, TreeNode *x)
{
	/*the TSN_7_12 must be initialized like this: memset(&value.RIMFrame.TSN_7_12, '\0', sizeof(struct UniqueSerialNumber));*/
	return memcmp(&value_sn, &x->serialNumber, sizeof(struct UniqueSerialNumber));
}

void insert_newNode(Timer_Tik current_time, TreeNode2Field value, TreeNode *x, TreeNode **return_x) //return created TreeNode
{
	t_last = t_current;
	t_current = current_time;
	if(t_current - t_last_last <= T_UNIQUE*255)
	{
		++last_added_nodes_count;
	}
	else
	{
		if(t_current - t_last_last <= 2*T_UNIQUE*255)
		{
			last_last_added_nodes_count = last_added_nodes_count;
		}
		else
		{
			last_last_added_nodes_count = 0;
		}
		last_added_nodes_count = 1;
		t_last_last = t_current;
	}
	short x_arp_current_time = arp_current_time + ((t_current - t_last) / T_UNIQUE)%255;
	arp_current_time += x_arp_current_time % 255;
	insert_treeNode(value, x, 1, &*return_x);
	if(*return_x == 0)
		--last_added_nodes_count;
}
/*return created TreeNode, don't use this function by another module*/
void insert_treeNode(TreeNode2Field value, TreeNode *x, char isTimerOn, TreeNode **return_x)
{
	if(x == 0)
		return;
	if(*return_x != 0)
		free(*return_x);
	if(treeNode_memcmp(value.serialNumber, x) == 0)
	{
		/*the current device already exist in this TreeNode, and we discarded it by returning NULL pointer*/
		*return_x = 0;
		return;
	}
	else if(treeNode_memcmp(value.serialNumber, x) < 0)
	{
		if(x->left != POINTER_ON_NULL)
		{
			TreeNode *get_xl;
			get_fromFlash(x, left, &get_xl);
			insert_treeNode(value, get_xl, isTimerOn, &*return_x);
			free_treeNode(&get_xl);
		}
		else
		{
			x->left = value.Link_ID;
			TreeNode *l_added_TreeNode;
			read_fromFlash(last_added_TreeNode, &l_added_TreeNode);
			l_added_TreeNode->next = value.Link_ID;
			write_intoFlash(l_added_TreeNode);
			get_fromFlash(x, left, &*return_x);
			((TreeNode *)*return_x)->serialNumber = value.serialNumber;
			((TreeNode *)*return_x)->Link_ID = value.Link_ID;
			((TreeNode *)*return_x)->top = x->Link_ID;
			/*Sets the left child of the child node to null*/
			((TreeNode *)*return_x)->left = POINTER_ON_NULL;
			/*Sets the right child of the child node to null*/
			((TreeNode *)*return_x)->right = POINTER_ON_NULL;
			/*already this is the latest TreeNode*/
			((TreeNode *)*return_x)->next = POINTER_ON_NULL;
			((TreeNode *)*return_x)->prev = l_added_TreeNode->Link_ID;
			if(isTimerOn == 1)
				((TreeNode *)*return_x)->timer = arp_current_time;
			rootInTree->prev = ((TreeNode *)*return_x)->Link_ID;
			last_added_TreeNode = ((TreeNode *)*return_x)->Link_ID;
			write_intoFlash(x);
			write_intoFlash(*return_x);
			free_treeNode(&l_added_TreeNode);
			return;
		}
	}
	else if(treeNode_memcmp(value.serialNumber, x) > 0)
	{
		if(x->right != POINTER_ON_NULL)
		{
			TreeNode *get_xl;
			get_fromFlash(x, right, &get_xl);
			insert_treeNode(value, get_xl, isTimerOn, &*return_x);
			free_treeNode(&get_xl);
		}
		else
		{
			x->right = value.Link_ID;
			TreeNode *l_added_TreeNode;
			read_fromFlash(last_added_TreeNode, &l_added_TreeNode);
			l_added_TreeNode->next = value.Link_ID;
			write_intoFlash(l_added_TreeNode);
			get_fromFlash(x, right, &*return_x);
			((TreeNode *)*return_x)->serialNumber = value.serialNumber;
			((TreeNode *)*return_x)->Link_ID = value.Link_ID;
			((TreeNode *)*return_x)->top = x->Link_ID;
			/*Sets the left child of the child node to null*/
			((TreeNode *)*return_x)->left = POINTER_ON_NULL;
			/*Sets the right child of the child node to null*/
			((TreeNode *)*return_x)->right = POINTER_ON_NULL;
			/*already this is the latest TreeNode*/
			((TreeNode *)*return_x)->next = POINTER_ON_NULL;
			((TreeNode *)*return_x)->prev = l_added_TreeNode->Link_ID;
			if(isTimerOn == 1)
				((TreeNode *)*return_x)->timer = arp_current_time;
			rootInTree->prev = ((TreeNode *)*return_x)->Link_ID;
			last_added_TreeNode = ((TreeNode *)*return_x)->Link_ID;
			write_intoFlash(x);
			write_intoFlash(*return_x);
			free_treeNode(&l_added_TreeNode);
			return;
		}
	}
}

/*getting treeNode by serial number*/
void get_treeNode(struct UniqueSerialNumber value_sn, TreeNode *x, TreeNode **return_x)
{
	if(x == 0)
	{
		*return_x = 0;
		return;
	}
	if(treeNode_memcmp(value_sn, x) == 0)
	{
		*return_x = (TreeNode *)malloc(sizeof(TreeNode));
		**return_x = *x;
		return;
	}
	else if(treeNode_memcmp(value_sn, x) < 0)
	{
		TreeNode *x_left;
		get_fromFlash(x, left, &x_left);
		get_treeNode(value_sn, x_left, &*return_x);
		free_treeNode(&x_left);
	}
	else if(treeNode_memcmp(value_sn, x) > 0)
	{
		TreeNode *x_right;
		get_fromFlash(x, right, &x_right);
		get_treeNode(value_sn, x_right, &*return_x);
		free_treeNode(&x_right);
	}
}
/*
//void delete_treeNode(TreeNode2Field value, TreeNode *x);
//this function delete the value tree node and its chains from x, into flash
//call this function, when you sure, that device (which node you want to delete) is disconnected
*/
void delete_treeNode(TreeNode2Field value, TreeNode *x)
{
	if(x == 0)
		return;
	if(treeNode_memcmp(value.serialNumber, x) == 0)
	{
		TreeNode *x_next;
		get_fromFlash(x, next, &x_next);
		TreeNode *x_prev;
		get_fromFlash(x, prev, &x_prev);
		if(x_next != 0)
		{
			x_prev->next = x_next->Link_ID;
			x_next->prev = x_prev->Link_ID;
			write_intoFlash(x_next);
			write_intoFlash(x_prev);
			free_treeNode(&x_next);
			free_treeNode(&x_prev);
		}
		else
		{
			x_prev->next = POINTER_ON_NULL;
			last_added_TreeNode = x_prev->Link_ID;
			write_intoFlash(x_prev);
			free_treeNode(&x_prev);
		}

		TreeNode *x_right;
		get_fromFlash(x, right, &x_right);
		TreeNode *x_left;
		get_fromFlash(x, left, &x_left);
		if(x_left != 0 || x_right != 0)
		{
			TreeNode *topx;
			get_fromFlash(x, top, &topx);
			if(x_left != 0)
			{
				if(topx->left == x->Link_ID)
					topx->left = x->left;
				else
					topx->right = x->left;
				x_left->top = topx->Link_ID;
				TreeNode *rx;
				if(x_right != 0)
				{
					insert_treeNode(*x_right, x_left, 0, &rx);
					rx->left = x_right->left;
					rx->right = x_right->right;
				}
				write_intoFlash(x_left);
				write_intoFlash(topx);
				write_intoFlash(rx);
				free_treeNode(&x_left);
				free_treeNode(&x_right);
				free_treeNode(&rx);
			}
			else
			{
				if(topx->left == x->Link_ID)
					topx->left = x->right;
				else
					topx->right = x->right;
				x_right->top = topx->Link_ID;
				write_intoFlash(x_right);
				write_intoFlash(topx);
				free_treeNode(&x_right);
			}
			free_treeNode(&topx);
		}
		free_treeNode(&x);
	}
	else if(treeNode_memcmp(value.serialNumber, x) < 0)
	{
		TreeNode *x_left;
		get_fromFlash(x, left, &x_left);
		delete_treeNode(value, x_left);
		free_treeNode(&x_left);
		free_treeNode(&x);
	}
	else if(treeNode_memcmp(value.serialNumber, x) > 0)
	{
		TreeNode *x_right;
		get_fromFlash(x, right, &x_right);
		delete_treeNode(value, x_right);
		free_treeNode(&x_right);
		free_treeNode(&x);
	}
}


/*
//void delete_treeNode_byLinkID(unsigned char Link_ID, TreeNode *x)
//this function delete the tree node (by LinkID) and its chains from x, into flash
//call this function, when you sure, that device (which node you want to delete) is disconnected
*/
void delete_treeNode_byLinkID(unsigned char Link_ID)
{
	if(Link_ID == ROOT_LINK_ID)
		return;

	TreeNode *x;
	read_fromFlash(Link_ID, &x);
	TreeNode2Field value = *x;
	delete_treeNode(value, x);//value == *x => delete_treeNode(value, x) == delete_treeNode(*x, x) => x will be deleted
	free_treeNode(&x);
}
/*
//call "void delete_Nodes_greater_x_time(char x_time);" function, if you need to delete
//all nodes, which lying into arp table long time than x_time
*/
void delete_Nodes_greater_x_time(char x_time)
{
	char l_added_nodes_count = last_added_nodes_count;
	char l_l_added_nodes_count = last_last_added_nodes_count;
	char start_for_deleting;
	char is_arpLessThan_x_time = 0;
	if(arp_current_time < x_time)
	{
		is_arpLessThan_x_time = 1;
		start_for_deleting = (255 - x_time) + arp_current_time;
	}
	else
	{
		is_arpLessThan_x_time = 0;
		start_for_deleting = arp_current_time - x_time;
	}
	TreeNode *x;
	get_fromFlash(rootInTree, prev, &x);
	while(x->Link_ID != ROOT_LINK_ID)
	{
		if(is_arpLessThan_x_time == 0)
		{
			while(x->Link_ID != ROOT_LINK_ID)
			{
				TreeNode *x1 = x;
				get_fromFlash(x1, prev, &x);
				if(l_added_nodes_count > 0)
					--l_added_nodes_count;
				if(x->timer < start_for_deleting || l_added_nodes_count <= 0)
					delete_treeNode_byLinkID(x1->Link_ID);
				free_treeNode(&x1);
			}
			free_treeNode(&x);
		}
		else
		{
			while(l_added_nodes_count-- != 0)
			{
				TreeNode *x1 = x;
				get_fromFlash(x1, prev, &x);
				free_treeNode(&x1);
			}
			while(l_l_added_nodes_count-- != 0)
			{
				TreeNode *x1 = x;
				get_fromFlash(x1, prev, &x);
				if(x->timer < start_for_deleting)
					delete_treeNode_byLinkID(x1->Link_ID);
				free_treeNode(&x1);
			}
			while(x->Link_ID != ROOT_LINK_ID)
			{
				TreeNode *x1 = x;
				get_fromFlash(x1, prev, &x);
				delete_treeNode_byLinkID(x1->Link_ID);
				free_treeNode(&x1);
			}
			free_treeNode(&x);
		}
	}
}

void get_fromFlash(TreeNode *treeNode, relational_address pos, TreeNode **return_x)
{
	switch(pos)
	{
	case left:
	{
		if(treeNode->left == POINTER_ON_NULL)
		{
			*return_x = 0;
			return;
		}
		/*the TreeNode of treeNode->left address must be returned*/
		read_fromFlash(treeNode->left, &*return_x);
	}
	break;
	case right:
	{
		if(treeNode->right == POINTER_ON_NULL)
		{
			*return_x = 0;
			return;
		}
		/*the TreeNode of treeNode->right address must be returned*/
		read_fromFlash(treeNode->right, &*return_x);
	}
	break;
	case top:
	{
		/*the TreeNode of treeNode->top address must be returned*/
		read_fromFlash(treeNode->top, &*return_x);
	}
	break;
	case next:
	{
		if(treeNode->next == POINTER_ON_NULL || treeNode->next == ROOT_LINK_ID)
		{
			*return_x = 0;
			return;
		}
		/*the TreeNode of treeNode->next address must be returned*/
		read_fromFlash(treeNode->next, &*return_x);
	}
	break;
	case prev:
	{
		if(treeNode->prev == POINTER_ON_NULL)
		{
			*return_x = 0;
			return;
		}
		/*the TreeNode of treeNode->prev address must be returned*/
		read_fromFlash(treeNode->prev, &*return_x);
	}
	break;
	}
}

void write_intoFlash(TreeNode *treeNode)
{
	int real_address = flash_address;
	if(treeNode->Link_ID != ROOT_LINK_ID)
	{
		/*the beginning of flesh is written our root instance*/
		real_address += (treeNode->Link_ID + 1);
	}
	//write treeNode into this address of flash: (flash_address + treeNode->data.Link_ID + 1)//eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
}

/*this function delete TreeNode object from RAM*/
void free_treeNode(TreeNode **x)
{
	if(*x == 0 || *x == rootInTree)
		return;
	free(*x);
	*x = 0;
}

/*call this function by giving it LinkID as address, if there is not any node by this LinkID,
//this function would return 0 pointer
 */
void read_fromFlash(unsigned char address, TreeNode **return_x)
{
	if((is_arp_i_not_null[address/8] & (128 >> (address%8))) == 0)
	{
		*return_x = 0;
	}
	int real_address = flash_address;
	*return_x = (TreeNode*)malloc(sizeof(TreeNode));
	if(address != ROOT_LINK_ID)
	{
		/*the beginning of flesh is written our root instance*/
		real_address += (address + 1);
		///
		//here we must initialize rx by reading from flash //eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
		///
	}
	else
	{
		**return_x = *rootInTree;
	}
}
